from typing import *
from heapq import heappush, heappop


class Solution:

    def filterRestaurants(self, restaurants: List[List[int]],
                          veganFriendly: int, maxPrice: int,
                          maxDistance: int) -> List[int]:
        # restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]
        q = []
        for id, rat, veg, pri, dis in restaurants:
            if pri <= maxPrice and dis <= maxDistance:
                if veganFriendly == 1:
                    if veg == 1:
                        heappush(q, (-rat, -id))
                else:
                    heappush(q, (-rat, -id))

        ans = []
        while q:
            ans.append(-heappop(q)[1])
        return ans

class Solution:

    def filterRestaurants(self, restaurants: List[List[int]],
                          veganFriendly: int, maxPrice: int,
                          maxDistance: int) -> List[int]:
        q = []
        for id, rat, veg, pri, dis in restaurants:
            if pri <= maxPrice and dis <= maxDistance and (veganFriendly == 1 and veg == 1 or veganFriendly == 0):
                q.append([id,rat])
        q.sort(key= lambda a : (-a[1],-a[0]))

        return [v[0] for v in q]